#include "headfiles.h"

using namespace std;

vector<vector<int> > fourSum(vector<int> &num, int target) {
    sort(num.begin(), num.end());
    int size = num.size();
    int start, end, i, j;
    vector<vector<int>> output;
    for (start = 0; start < size - 3; start++) {
        if (start > 0 && num[start] == num[start - 1]) {
            start++;
            continue;
        }
        
        for (end = start + 3; end < size; end++) {
            if (end > start + 3 && num[end] == num[end - 1]) {
                end++;
                continue;
            }
            
            i = start + 1;
            j = end - 1;
            
            while (i < j) {
                if (i > start + 1 && num[i] == num[i - 1]) {
                    i++;
                    continue;
                }
                
                if (j < end - 1 && num[j] == num[j + 1]) {
                    j--;
                    continue;
                }
                
                int sum = num[i] + num[j] + num[start] + num[end];
                if (sum == target) {
                    vector<int> res;
                    res.push_back(num[start]);
                    res.push_back(num[i]);
                    res.push_back(num[j]);
                    res.push_back(num[end]);
                    output.push_back(res);
                    i++;
                    j--;
                }
                else if (sum < target) {
                    i++;
                }
                else {
                    j--;
                }
            }
        }
    }
    
    return output;
}

